package DP1;

import javax.print.DocFlavor;
import java.util.Arrays;

/**
 * 零钱兑换
 */
public class Main19 {
    public static void main(String[] args) {
        int[] coins = {1,2,5};
        int amount = 11;
        System.out.println(help1(coins,amount));
    }

    public static int coinChange(int[] coins, int amount) {
        if(coins.length == 0) return -1;
        int nums = coins.length;
        int[][] dp = new int[nums + 1][amount + 1];//dp[i][j]代表前i个***的钱加起来为j最少个数
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], amount+1);
            if (i > 0) dp[i][0] = 0;
        }
        for (int i = 1; i <= nums; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j < coins[i - 1]) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
            }
        }
        return dp[nums][amount]== amount+1? -1:dp[nums][amount];
    }

    public static int help(int[] coins, int amount){
        if(coins.length == 0) return -1;
        int num = coins.length;
        int[][] dp = new int[num+1][amount+1];

        // 初始化
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],amount+1);
            if(i>0) dp[i][0] = 0;
        }

        for (int i = 1; i <= num; i++) {
            for (int j = 1; j <= amount; j++) {
                if(j < coins[i-1]){
                    dp[i][j] = dp[i-1][j];   // 如果要组成的总钱数比当前的面值小
                }else{
                    dp[i][j] = Math.min(dp[i-1][j],dp[i][j-coins[i-1]]+1);
                }
            }
        }

        return dp[num][amount] == amount+1 ? -1:dp[num][amount];
    }


    public static int help1(int[] coins, int amount){
        int nums = coins.length;
        Arrays.sort(coins);
        int[] dp = new int[amount + 1];//dp[i][j]代表前i个***的钱加起来为j最少个数
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for (int j = 1; j <= amount; j++) {
            for (int i = 0; i < nums; i++) {
                if (j >= coins[i])
                    dp[j] = Math.min(dp[j], dp[j - coins[i]]+1 );
            }
        }
        return dp[amount] == amount+1? -1:dp[amount];
    }


}
